// Package order_by_hot 2_199
// @Title order_by_hot
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/3 16:24
// @Create  2021/9/3 16:24
package order_by_hot

// RightSideView 返回二叉树的右视图  这里有个最大的坑，如果右节点没有数据，那么久要返回左节点了 层序遍历嘛
// 使用BFS实现
func RightSideViewBFS(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			if i == size-1 {
				ans = append(ans, node.Val)
			}
		}
	}
	return ans
}

// 使用DFS怎么做呢？

// RightSideViewDFS 使用DFS实现
func RightSideViewDFS(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)
	var dfs = func(root *TreeNode, depth int) {}
	dfs = func(root *TreeNode, depth int) {
		if root == nil {
			return
		}
		if depth == len(ans) {
			ans = append(ans, root.Val)
		}
		depth++
		dfs(root.Right, depth)
		dfs(root.Left, depth)
	}
	dfs(root, 0)
	return ans
}
